#include<stdio.h>
#include<stdlib.h>

typedef struct tree {
	int data;
	int height;
	struct tree* left;
	struct tree* right;
}Tree;

struct node {
	Tree* head;
};

// 返回树的高度
int getHeight(Tree* root) {
	return root ? root->height : 0;
}

// 取左右子树高度的最大值
int max(int a, int b) {
	return a > b ? a : b;
}

// 右右旋转
void rrRotation(Tree* node, Tree** root) {
	Tree* temp = node->right;//node 是第一个节点
	node->right = temp->left; // temp是失衡节点的父节点
	temp->left = node;
	node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
	temp->height = max(getHeight(temp->left), getHeight(temp->right)) + 1;
	*root = temp;
}

// 左左旋转
void llRotation(Tree* node, Tree** root) {
	Tree* temp = node->left;
	node->left = temp->right;
	temp->right = node;
	node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
	temp->height = max(getHeight(temp->left), getHeight(temp->right)) + 1;
	*root = temp;
}

Tree* insert(Tree* root, int value) {
	if (!root) {
		root = (Tree*)malloc(sizeof(Tree));
		root->data = value;
		root->left = NULL;
		root->right = NULL;
	}
	else {
		if (value < root->data) {  // 进入左子树
			root->left = insert(root->left, value);
			//拿到当前节点的左右子树的高度
			int lHeight = getHeight(root->left);
			int rHeight = getHeight(root->right);
			// 判断高度差
			if (lHeight - rHeight == 2) {
				// 判断失衡节点 node 在 root 的哪侧
				if (value < root->left->data) {
					// LL
					llRotation(root, &root);
				}
				else {
					//LR
					rrRotation(root->left, &root->left);
					llRotation(root, &root);
				}
			}
		}
		else if (value >= root->data) {
			root->right = insert(root->right, value);
			// 拿到当前节点左右子树的高度
			int lHeight = getHeight(root->left);
			int rHeight = getHeight(root->right);
			//判断高度差
			if (rHeight - lHeight == 2) {
				//判断失衡节点node在root的哪侧
				if (value >= root->right->data) {
					//RR
					rrRotation(root, &root);
				}
				else {
					//RL
					llRotation(root->right, &root->right);
					rrRotation(root, &root);
				}
			}
		}
		else {
			root = insert(root, value);
		}
	}
	// 更新高度
	root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
	return root;
}

void preOrder(Tree* root) {
	if (root) {
		printf("%d\t", root->data);
		preOrder(root->left);
		preOrder(root->right);
	}
}

int main() {

	struct node* link = (struct node*)malloc(sizeof(struct node));
	link->head = NULL;

	int a[] = { 1,2,3,4,5,6,7,8,9,-1 };
	for (int i = 0; a[i] != -1; i++) {
		link->head = insert(link->head, a[i]);
	}

	preOrder(link->head);


	return 0;
}